<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Hard
  </div>
  <div>
   <h1 class="question_title">
    977. Distinct Subsequences II
   </h1>
   <p>
    Given a string
    <code>
     S
    </code>
    , count the number of distinct, non-empty subsequences of
    <code>
     S
    </code>
    .
   </p>
   <p>
    Since the result may be large,
    <strong>
     return the answer modulo
     <code>
      10^9 + 7
     </code>
    </strong>
    .
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     Example 1:
    </strong>
   </p>
   <pre>
<strong>Input: </strong><span id="example-input-1-1">"abc"</span>
<strong>Output: </strong><span id="example-output-1">7</span>
<span><strong>Explanation</strong>: The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".</span>
</pre>
   <div>
    <p>
     <strong>
      Example 2:
     </strong>
    </p>
    <pre>
<strong>Input: </strong><span id="example-input-2-1">"aba"</span>
<strong>Output: </strong><span id="example-output-2">6
</span><strong>Explanation</strong>: The 6 distinct subsequences are "a", "b", "ab", "ba", "aa" and "aba".
</pre>
    <div>
     <p>
      <strong>
       Example 3:
      </strong>
     </p>
     <pre>
<strong>Input: </strong><span id="example-input-3-1">"aaa"</span>
<strong>Output: </strong><span id="example-output-3">3
</span><strong>Explanation</strong>: The 3 distinct subsequences are "a", "aa" and "aaa".
</pre>
    </div>
   </div>
   <p>
    &nbsp;
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     Note:
    </strong>
   </p>
   <ol>
    <li>
     <code>
      S
     </code>
     contains only lowercase letters.
    </li>
    <li>
     <code>
      1 &lt;= S.length &lt;= 2000
     </code>
    </li>
   </ol>
   <div>
    <p>
     &nbsp;
    </p>
    <div>
     <div>
      &nbsp;
     </div>
    </div>
   </div>
  </div>
  <div>
   <h1 class="question_title">
    977. 不同的子序列 II
   </h1>
   <p>
    给定一个字符串&nbsp;
    <code>
     S
    </code>
    ，计算&nbsp;
    <code>
     S
    </code>
    &nbsp;的不同非空子序列的个数。
   </p>
   <p>
    因为结果可能很大，所以
    <strong>
     返回答案模
    </strong>
    <strong>
     <code>
      10^9 + 7
     </code>
    </strong>
    .
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     示例 1：
    </strong>
   </p>
   <pre><strong>输入：</strong>"abc"
<strong>输出：</strong>7
<strong>解释：</strong>7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。
</pre>
   <p>
    <strong>
     示例 2：
    </strong>
   </p>
   <pre><strong>输入：</strong>"aba"
<strong>输出：</strong>6
<strong>解释：</strong>6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。
</pre>
   <p>
    <strong>
     示例 3：
    </strong>
   </p>
   <pre><strong>输入：</strong>"aaa"
<strong>输出：</strong>3
<strong>解释：</strong>3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。
</pre>
   <p>
    &nbsp;
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     提示：
    </strong>
   </p>
   <ol>
    <li>
     <code>
      S
     </code>
     &nbsp;只包含小写字母。
    </li>
    <li>
     <code>
      1 &lt;= S.length &lt;= 2000
     </code>
    </li>
   </ol>
   <p>
    &nbsp;
   </p>
   <p>
    &nbsp;
   </p>
  </div>
 </body>
</html>